The background description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the presently named inventors, to the extent it is described in this background section, as well as aspects of the description that may not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted as prior art against the present disclosure.
Numerous applications in computer vision, geographic services, gaming, etc. implement algorithms for characterizing the shape or bounds of a region, which may be defined by a collection of points and/or polygons. In general, the existing techniques are based on characterizing points and polygons in two- and three-dimensional spaces using bounding hulls (or alpha shapes or representative shapes). These techniques include computation of power crusts, chi shapes, and other generalizations of bounding hulls. However, these approaches often fail to narrowly describe the underlying constituent geometry of such regions. Although there is a single minimal-area convex hull which can be computed efficiently for a set of points, the minimal-area convex often does not meaningfully represent the visual “shape” of the set of points. Moreover, concave hull construction often requires careful analysis of the input data to determine meaningful resolutions at which data should be sampled as well as to define the level of allowable concavity. The creation of a visually representative concave hull may require further tuning, depending on the algorithm being used, thus further increasing computational cost.